//
// Description: 560. 和为 K 的子数组
// Created by Loading on 2021/9/24.
//

#include <bits/stdc++.h>

using namespace std;

int subarraySum(vector<int> &nums, int k) {
    // 统计前缀和出现的次数
    unordered_map<int, int> m;
    m[0]++;
    // 前缀和
    int pre = 0;

    int res = 0;
    for (auto &x : nums) {
        pre += x;
        /* 如果 pre - k 这个前缀和的值出现，表示从这个值出现的位置到当前位置的区间和为 k */
        res += m[pre - k];
        m[pre]++;
    }

    return res;
}

int main() {
    vector<int> nums = {1, 1, 1};
    int k = 2;
    int res = subarraySum(nums, k);
    cout << res << endl;

    return 0;
}